package com.company.bs2024;

/**
 * 常用算法说明类
 * <p>八皇后问题：
 * <pre>
 *     规则：在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意 两个皇后 都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
 * </pre>
 *
 * @author JianFeng Zhang(张建锋)
 * @date 2024-03-27 22:01:14
 */
public class First {

    /* 递归 Recursion
     * 递归的概念
     * 简单说：递归就是方法自己调用自己，每次调用时 传入不同的变量
     *
     * 是从问题入手，自底向上来解决问题。
     */

    // 共有多少个皇后
    int max = 8;
    /**
     * 存放皇后位置的结果
     * <pre>
     * 下标：表示棋盘中的某一行
     * 对应的值：表示在这一行上，该皇后摆放在哪一列
     * 比如：array[0] = 1，表示在第 1 行的第 2 列上摆放了一个皇后
     *
     * 由于规则，一行只能有一个皇后，所以可以使用一维数组来代替二维数组的棋盘结果
     * </pre>
     */
    int[] board = new int[max];
    int count = 0; // 统计有多少个结果

    public static void main(String[] args) {
        First first = new First();

        //从第1行开始放
        first.queue8(0);
    }

    private boolean queue8(int row) {
        //如果都放好了，没有问题
        //那么表示放第 9 个皇后，8 个皇后已经放完了
        // 表示找到了一个正确的结果，打印这个结果，并返回
        if (row == max) {
            count++;
            print();
            return true;
        }
        // 开始暴力对比，从该行的第一列开始尝试放置皇后，直到与前面所放置的不冲突
        for (int coulumn = 0; coulumn < board.length; coulumn++) {

            // 在该行的第 coulumn 列上放置一个皇后
            board[row] = coulumn;
            // 检测与已经放置的是否冲突
            if (judge(row)) {
                // 如果不冲突，则表示该行的皇后放置没有问题,开始进入下一行的皇后放置,看看下一行是否能找到位置
                // 如果可以，说明到第coulumn列的摆放是合法的。
                // 如果不可以，说明不能在第row行第coulumn列放一个皇后
                // 如果找不到一个合适的位置，就要回溯到上一列，重新测试新位置。
                if (!queue8(row + 1)) {
                    // 把row行column列的皇后拿走
                    board[row] = 0;
                }
            }
        }
        return false;
    }

    /**
     * 判定要放置的这一个皇后，和前面已经摆放的位置是否冲突
     *
     * @param n 第 n 个皇后
     * @return
     */
    private boolean judge(int n) {
        for (int i = 0; i < n; i++) {
            if (
                    /*
                     如果他们的摆放位置一样，说明是在同一列
                      x ....
                      x ....
                     */
                    board[i] == board[n]
                            /*
                              检测是否是同一斜列
                              下标: 代表的是第几行
                              值：代表的是第几列
                              . x . . .  n = 1,value = 1
                              x . . . .  i = 0,value = 0
                              Math.abs(n - i) = 1
                              Math.abs(array[n] - array[i]) = 1

                              . . x . .  n = 1,value = 2
                              . x . . .  i = 0,value = 1
                              Math.abs(n - i) = 1
                              Math.abs(array[n] - array[i]) = 1
                             */
                            || Math.abs(n - i) == Math.abs(board[n] - board[i])
            ) {
                return false;
            }
        }
        return true;
    }

    /**
     * 打印皇后的位置
     */
    private void print() {
        System.out.printf("第 %02d 个结果 ：", count);
        for (int i = 0; i < board.length; i++) {
            System.out.print(board[i] + " ");
        }
        System.out.println();
    }

}
